1. Field of the Invention
The present invention relates to routing packets through a network based on header information in a packet received at a network device; and, in particular, to increasing efficiency by classifying the packet as a member of a flow using hardware in which new flow identifiers are stored to prevent sending the same new flow more than once to a general-purpose processor.
2. Description of the Related Art
Networks of general purpose computer systems and special-purpose electronic devices connected by external communication links are well known. The networks often include one or more network devices that facilitate the passage of information between the computer systems and special-purpose devices. A network node is a network device, special-purpose device or computer system connected by the communication links.
Information is exchanged between network nodes according to one or more of many well known, new or still developing protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other based on information sent over the communication links. The protocols are effective at different layers of operation within each node, from generating and receiving physical signals of various types, to selecting a link for transferring those signals, to the format of information indicated by those signals, to identifying which software application executing on a computer system sends or receives the information. The conceptually different layers of protocols for exchanging information over a network are described in the Open Systems Interconnection (OSI) Reference Model. The OSI Reference Model is generally described in more detail in Section 1.1 of the reference book entitled Interconnections Second Edition, by Radia Perlman, published September 1999, which is hereby incorporated by reference as though fully set forth herein.
Communications between nodes are typically effected by exchanging discrete packets of data. Each packet typically comprises 1] header information associated with a particular protocol, and 2] payload information that follows the header information and contains information to be processed independently of that particular protocol. In some protocols, the packet includes 3] trailer information following the payload and indicating the end of the payload information. The header includes information such as the source of the packet, its destination, the length of the payload, and other properties used by the protocol. Often, the data in the payload for the particular protocol includes a header and payload for a different protocol associated with a different, usually higher, layer of the OSI Reference Model. The header for a particular protocol typically indicates a type for the next protocol contained in its payload. The next protocol layer is said to be encapsulated in the first layer protocol. The headers included in a packet traversing multiple heterogeneous networks, such as the Internet, typically include a physical (layer 1) header, a data-link (layer 2) header, an internetwork (layer 3) header and a transport (layer 4) header, as defined by the Open Systems Interconnection (OSI) Reference Model.
Routers and switches are network devices that determine which communication link or links to employ to support the progress of packets through the network. Routers and switches can employ software executed by a general purpose processor, called a central processing unit (CPU), or can employ special purpose hardware, or can employ some combination to make these determinations and forward the packets from one communication link to another. Switches typically rely on special purpose hardware to quickly forward packets based on one or more specific protocols. For example, Ethernet switches for forwarding packets according to Ethernet protocol are implemented primarily with special purpose hardware.
While the use of hardware processes packets extremely quickly, there are drawbacks in flexibility. As protocols evolve through subsequent versions and as new protocols emerge, the network devices that rely on hardware become obsolete and have to ignore the new protocols or else be replaced. As a consequence, many network devices, such as routers, which forward packets across heterogeneous data link networks, include a CPU that operates according to an instruction set (software) that can be modified as protocols change.
Software executed operations in a CPU proceed more slowly than hardware executed operations, so there is a tradeoff between flexibility and speed in the design and implementation of network devices.
Some current routers implement sophisticated algorithms that provide high performance forwarding of packets based on combining two or more fields in one or more headers. For example, instead of making forwarding decisions separately on each packet in a stream of related packets directed from the same source node to the same destination node, these routers identify the packet stream from a unique signature derived from the layer 2, layer 3 and layer 4 header information and forward each member of the stream according to the same decision made for the first packet in the stream. The packets that have the same signature are said to belong to the same packet stream or flow.
The throughput of many current routers is limited by the processing capacity of the CPU, i.e., the router performance is said to be CPU limited. To improve throughput of such routers, it is desirable to relieve the CPU load and replace some of the software functionality with hardware functionality, without losing the flexibility to adapt to evolving protocols. In particular, there is a desire to relieve the CPU of determining what flow a packet belongs to.
In one approach, a combination of one or more special purpose circuit blocks (hardware) is configured to determine the flow of a data packet received at the router. The hardware identifies the flow for the CPU by determining which of multiple previously identified flows the packet belongs to. The previously identified flows are stored in a flow data structure that the CPU has access to, such as a linked list data structure. In this approach, when a data packet arrives with a signature that does not match that of a flow in the linked list, the flow is called a missed flow—it is missing in the flow data structure. The missed flow identified in the first packet of that flow is sent to the CPU and the CPU adds the new flow to the flow data structure, e.g., the linked list.
An advantage of this approach is that the CPU is saved significant processing cycles, and hence time, by referencing previously stored information associated with each entry in the flow data structure that describes processing requirements for the flow.
A problem arises in this approach because multiple packets of the same flow often arrive in close succession. Thus there is a good chance the second packet of a flow arrives, to be classified by the hardware, before the CPU has finished adding the flow's signature from the first packet to the flow data structure. When the hardware finds the flow of the second packet missing, it would send the signature of the second packet to the CPU as a missed flow. The CPU would then add the same flow a second time to the flow data structure. Depending on the latency period for the CPU process to add the flow, the same flow would be entered into the data structure two, three or more times.
A problem with multiple entries in the flow data structure is that particular information associated with the flow will be associated with only one linked list entry and all the information may be spread over two or more linked list entries as new entries for the same flow are added to the head of the list. The CPU is then unable to find all the processing information needed in a flow linked list entry. CPU processing time is wasted computing and determining processing information that was already determined for the same flow earlier but stored in a different linked list entry.
One approach to prevent the multiple entries into the flow linked list is to have the CPU check each entry, after receiving missed flow data from the hardware, to ensure that the signature for the missed flow received from the hardware is not already in the linked list. A disadvantage of this approach is that CPU time is expended to check the list, thus reducing the capacity of the CPU to perform other tasks. With a CPU-limited router, the extra processing significantly decreases the router's throughput.
Based on the foregoing, there is a clear need to provide a hardware assist to ensure that the CPU adds one and only one entry to the flow data structure, such as the linked list, for each unique signature in one or more missed flows. Subsequent packets with the same signature must be recognized by the hardware circuit as belonging to the one and only one entry in the data structure.
The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not to be considered prior art to the claims in this application merely due to the presence of these approaches in this background section.